package com.cat.dynamicPlanning;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/ways-to-express-an-integer-as-sum-of-powers/
 * @create 2025/9/1 20:05
 * @since JDK17
 */

public class Solution45 {
    static int N = ((int) (1e9 + 7));
    public int numberOfWays(int n, int x) {

        long[] dp = new long[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = n; j >= Math.pow(i, x); j--) {
                dp[j] += dp[((int) (j - Math.pow(i, x)))];
            }
        }
        return ((int) (dp[n] % N));
    }
}
